package Sort;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-04-18 15:09
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /*要求第0个位置不能有元素*/
    @Override
    public void sort(T[] nums) {
        int n=nums.length-1;
        for (int k = n/2; k >=1; k--) {
            sink(nums,k,n);
        }
        while (n>1){
            //将第一个元素和最后一个元素交换，然后将第一个元素下沉
            swap(nums,1,n--);
            sink(nums,1,n);
        }
    }

    //下沉：当一个节点比子节点来的小，那也需要向下不断交换
    private void sink(T[] nums,int k,int n){
        while (2*k<=n){
            int j=2*k;
            if (j<n&&less(nums,j,j+1)){
                j++;
            }
            if (!less(nums,k,j)){
                break;
            }
            swap(nums,k,j);
            k=j;
        }
    }
    private boolean less(T[] nums,int i,int j){
        return nums[i].compareTo(nums[j])<0;
    }

    public static void main(String[] args) {
        Integer[] nums={3,5,6,4,1,2};
        Integer[] num={-1,3,5,6,4,1,2};
        HeapSort<Integer> heapSort=new HeapSort<Integer>();
        heapSort.sort(num);
        for (int i = 0; i < nums.length; i++) {
            nums[i]=num[i+1];
        }
        System.out.println(Arrays.toString(nums));
    }
}
